class Node:
    def __init__(self,elem=-1,lchild=None,rchild=None):
        self.elem =elem
        self.lchild=lchild
        self.rchild=rchild


class BinaryTree:
    """
    二叉树类
    """
    def __init__(self):
        self.root=None
        self.help_queue=[]  #辅助队列

    def level_build_tree(self,node:Node):
        """
        二叉树建树
        """
        if self.root is None:
            self.root=node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:    #当前父节点左孩子为空
                self.help_queue[0].lchild = node     #添加左孩子
            else:
                self.help_queue[0].rchild = node    #添加右孩子
                self.help_queue.pop(0)              #父节点满，出队
            
    def pre_order(self,current_node:Node):
        """
        二叉树先序遍历
        """
        if current_node:
            print(current_node.elem,end='')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self,current_node:Node):
        """
        二叉树中序遍历
        """
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem,end='')
            self.mid_order(current_node.rchild)

    def last_order(self,current_node:Node):
        """
        二叉树后序遍历
        """
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem,end='')

    def level_order(self):
        help_queue =[]
        help_queue.append(self.root)                #根节点入队
        while help_queue:
            out_node:Node = help_queue.pop(0)       #出队
            print(out_node.elem,end='')
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1,10):
        new_node = Node(i)                          #实例化结点
        tree.level_build_tree(new_node)             #建树
    print('前序遍历二叉树：')
    tree.pre_order(tree.root)                       #前序遍历
    print('\n中序遍历二叉树：')
    tree.mid_order(tree.root)                       #中序遍历
    print('\n后序遍历二叉树：')
    tree.last_order(tree.root)  #后序遍历
    print('\n层次遍历二叉树：')
    tree.level_order()

